|
Constraint Handling Rules（CHR）は1991年にThom Frühwirthが発表した、ユーザ定義の制約が書けるように設計された宣言型プログラミング言語である〔 Frühwirth T., ''Introducing Simplification Rules''. Internal Report ECRC-LP-63, ECRC Munich, Germany, October 1991, Presented at the Workshop Logisches Programmieren, Goosen/Berlin, Germany, October 1991 and the Workshop on Rewriting and Constraints, Dagstuhl, Germany, October 1991.〕 〔Frühwirth T., ''Theory and Practice of Constraint Handling Rules''. Special Issue on Constraint Logic Programming (P. Stuckey and K. Marriott, Eds.), Journal of Logic Programming, Vol 37(1-3), October 1998.〕。 多重集合の書き換え規則に基づく制約処理モデルを特徴とし、ルールにより制約をより単純な制約に書き換えることで、様々な制約下での解を求める。CHRはチューリング完全だが〔Jon Sneyers, Tom Schrijvers, Bart Demoen: ''The computational power and complexity of constraint handling rules.'' ACM Trans. Program. Lang. Syst. 31(2): 2009.〕、 独立した言語としてではなく既存言語の拡張機能として、主にPrologなどのホスト言語上に実装されたライブラリとして提供される。 CHRの典型的な応用分野はアブダクションなどの推論サービス、マルチエージェントシステム、自然言語処理、スケジューリング、型システム、ソフトウェアのテストと診断、セマンティックウェブなどである。 == 概要 == ''Constraint Handling Rules''（CHR）はコミッテッドチョイス（committed-choice）型並行制約プログラミング言語で、ガード付き書換え規則により、原子論理式（制約）をより単純なものに書き換える。 CHRは元々制約充足系（constraint solver）の記述のために開発されたが、高水準の汎用の並行制約プログラミング言語としても用いられるようになってきた〔Frühwirth T., ''Constraint Handling Rules - The Story So Far''. Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, p.13-14, July 10-12, 2006.〕。 CHRの特徴は以下の通りである。 * 頭部に制約の多重集合が書ける * 多重集合書換えに基づく言語の中では強力 * 多くの応用プログラムがある CHRは''単純化規則（Simplification rule）''と''伝播規則（Propagation rule）''、およびそれらの組み合わせである''単純化伝播規則（"Simpagation" rule）''からなる。 単純化規則（Simplification rule）は、複数の制約を論理的に等価なより単純な制約に変換する。(例えば、X≦Y, Y≦X ⇔ X=Y. や X≦X ⇔ true.) 伝播規則（Propagation rule）は、論理的には冗長だが単純化に結び付くような制約を新しく追加する。(例えば、X≦Y, Y≦Z ⇒ X≦Z.) これらの規則の組み合わせることにより、例えば A≦B, B≦C, C≦A は A=B, A=C に単純化される。 それぞれの規則は以下の形式で記述する。ヘッド(H) にマッチした要素がガード(G) の制約を満たすときにヘッドをボディ(B) に書き換える。ガード部がない（条件が"true"のみの）場合ガード部とその後のコミット演算子"|"は省略できる。RuleNameはルール名で、続く"@"と共に用いられ、省略可能である。 *単純化規則（Simplification rule） ''RuleName'' @ H1, ..., Hi ⇔ G1, ..., Gj| B1, ..., Bk . ヘッドH1, ...,Hiを除去して, ボディB1, ..., Bkを生成する。 *伝播規則（Propagation rule） ''RuleName'' @ H1, ..., Hi ⇒ G1, ..., Gj| B1, ..., Bk . ヘッドH1, ..., Hiを残したまま, ボディB1, ..., Bkを生成する。 *単純化伝播規則（Simpagation rule） ''RuleName'' @ H1, ..., Hh\ Hh+1, ..., Hi ⇔ G1, ..., Gj| B1, ..., Bk . ヘッドHh+1, ..., Hiを除去して, ボディB1, ..., Bkを生成する。 以下に順序集合を表す二項関係"≦"の制約を扱う、SWI-Prolog上での4つのCHRの規則からなるプログラムの例を示す。"%"以降はコメントを表す。 :- use_module(library(chr)). :- op(500, xfx, leq). :- chr_constraint leq/2. % X leq Y は変数Xが変数Yに対しless-or-equalの関係であることを示す reflexivity @ X leq X <=> true. % 反射律 antisymmetry @ X leq Y , Y leq X <=> X=Y. % 半対称律 idempotence @ X leq Y \ X leq Y <=> true. % 冪等性 transitivity @ X leq Y , Y leq Z ==> X leq Z. % 推移律 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Constraint Handling Rules」の詳細全文を読む スポンサード リンク
|